import java.util.Arrays;
import java.util.PriorityQueue;

public class AdvantageCount {
    int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        /*将nums1重新排序，使得nums1对nums2具有最大优势。所以nums2的顺序是不能改变的
        * 但是，我们的思路是“用nums1的最大值去比较nums2的最大值，如果比得过就比，比不过就用nums1的最小值去送人头
        * 所以又必须要对nums2进行排序”*/
        // 给 nums2 降序排序
        /*这里使用了一个带有构造器的最大堆。堆中的每一个结点是一个数组，数组中只有两个元素，
        * 一个是nums2中元素的索引，一个是该索引下的元素*/
        PriorityQueue<int[]> maxpq = new PriorityQueue<>(
                (int[] pair1, int[] pair2) -> {
                    return pair2[1] - pair1[1];
                }
        );
        for (int i = 0; i < n; i++) {
            maxpq.offer(new int[]{i, nums2[i]});
        }
        // 给 nums1 升序排序
        Arrays.sort(nums1);

        // nums1[left] 是最小值，nums1[right] 是最大值
        int left = 0, right = n - 1;
        int[] res = new int[n];

        while (!maxpq.isEmpty()) {
            int[] pair = maxpq.poll();
            // maxval 是 nums2 中的最大值，i 是对应索引
            int i = pair[0], maxval = pair[1];
            if (maxval < nums1[right]) {
                /*用nums1的最大值和nums2的最大值比较，如果前者大于后者，就将nums1中的这个值放在nums2对应的索引上*/
                // 如果 nums1[right] 能胜过 maxval，那就自己上
                res[i] = nums1[right];
                right--;
            } else {
                // 否则用最小值混一下，养精蓄锐
                res[i] = nums1[left];
                left++;
            }
        }
        return res;
    }

}
